//给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 
//
// 
//
// 在杨辉三角中，每个数是它左上方和右上方的数的和。 
//
// 示例: 
//
// 输入: 3
//输出: [1,3,3,1]
// 
//
// 进阶： 
//
// 你可以优化你的算法到 O(k) 空间复杂度吗？ 
// Related Topics 数组 
// 👍 175 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：杨辉三角 II
public class P119PascalsTriangleIi {

    /**
     *
     * 思路： 调上一题的
     *
     * 执行用时： 2 ms , 在所有 Java 提交中击败了 50.29% 的用户 内存消耗： 37.3 MB , 在所有 Java 提交中击败了 37.15% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<Integer>> list = new ArrayList<>();

        public List<Integer> getRow(int rowIndex) {
            rowIndex = rowIndex + 1;
            if (rowIndex > 0) {
                List<Integer> one = new ArrayList<>();
                one.add(1);
                list.add(one);

                for (int i = 1; i < rowIndex; i++) {
                    List<Integer> last = list.get(i - 1);
                    List<Integer> now = new ArrayList<>();

                    for (int k = 0; k <= last.size(); k++) {
                        // 头尾 填 1
                        if (k == 0 || k == last.size()) {
                            now.add(1);
                        } else {
                            now.add(last.get(k) + last.get(k - 1));
                        }
                    }
                    list.add(now);
                }
            }
            return list.get(rowIndex - 1);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P119PascalsTriangleIi().new Solution();
        System.out.println(solution.getRow(33));
        // TO TEST
    }

}